#include "nalgo.h"
#include<iostream>


int32_t mulinv(int32_t e, int32_t n)
{
	int x = 0, y = 1, u = 1, v = 0, a = e, b = n, m = 0, l = 0, q = 0, r = 0;
	while(a != 0) {
		q = b / a;
		r = b % a;
		m = x - u * q;
		l = y - v * q;
		b = a;
		a = r;
		x = u;
		y = v;
		u = m;
		v = l;
	}
	while( x < 0 )
		x += n;
	return x % n;		
} 

int32_t mod(int32_t e, int32_t x, int32_t n)
{
	int64_t m = 0;
	if(x > 0) {
		if(x == 1)
			return e % n;
		else if(x % 2 == 0)	{
			m = mod(e, x / 2, n);
			m *= m;
			return m % n;
		}
		else {
			m = mod(e, x - 1, n);
			m *= e;
			return m % n;
		}
	}
	else if(x == 0)
		return 1;
	else {
		if( x == -1 )
			return mulinv(e, n);
		else if(x % 2 == 0) {
			m = mod(e, x / 2, n);
			m *= m;
			return m % n;
		}
		else {
			m = mod(e, x - 1, n);
			m *= e;
			return m % n;
		}
	}	
}

bool isPrime( int n )
{
	int j = 0, m = n - 1, b = 0, i = 1, v = 0;
    do {
		j++;
		m /= 2;
    }while( m % 2 == 0 );
    srand( ( unsigned int )time( NULL ) );
    b = rand() % ( n - 2 ) + 2; 
    v = mod( b, m, n ) % n;
    while( v < 0 )
           v += n;
    if( v == 1 )
        return true; 
    while( 1 ) {
		if( v == n - 1 )
			return true;
		if( i == j )
			return false;
		v *= v;
		v %= n;
		while( v < 0 )
			v += n; 
		i++;
	}
}

cmsg_t rabinOTClientEncode(msg_t x, key_t k, key_t n, key_t e)
{	
	int32_t m = 0;
	m = mod(k, e, n);	
	m += x;	 
	while(m < 0)
		m += n;
	return m % n; 
}

cmsg_t rabinOTServerEncode(cmsg_t v, msg_t m, msg_t x, key_t d, key_t n)
{
	int k = 0, l = 0;
	k = v - x;
	l = mod(k, d, n);
	while(l < 0)
		l += n;   
	return m + l;
}

msg_t rabinOTDecode(cmsg_t mc, key_t k)
{
	return mc - k;
}
